/**
 * 
 */
package interval;

import java.util.Arrays;

import java.util.Collections;
import java.util.Comparator;
import java.util.Map;
import java.util.HashMap;
import java.util.ArrayList;

import utils.CreateUtils;
import utils.PrintUtils;

/**
 * @author Michael
 * Problem: Giving lots of intervals [ai, bi], find the interval (point) which intersects with the most number of intervals
 * For example, by given [1,5] [2,4],[3,6], [7,8], [8,10], it should return an interval [3,4].
 * However, if some of the starting/ending points are mixed, for example [1,3], [2,3], [3,4],[3,5], then the point 3 intersect with the most number of intervals and should be therefore returned.
 */
public class FindMostOverLappedInterval {

	public static enum PointType {
		BEGIN, END;
	}
	
	public static class IntervalPoint<T extends Comparable<? super T>>{	
		public T value;
		public PointType type;
		
		public IntervalPoint(T value, PointType type) {
			this.value = value;
			this.type = type;
		}
	}
	
	// Time O(n), Space O(n)
	public static <T extends Comparable<? super T>> Interval<T> findMostOverLappedInterval(Interval<T>[] arr) {
		assert (arr != null && arr.length > 0);
		
		ArrayList<IntervalPoint<T>> beginsAndEnds = new ArrayList<IntervalPoint<T>>(arr.length * 2);
		
		for (int i = 0; i < arr.length; ++i) {
			beginsAndEnds.add(2 * i, new IntervalPoint<T>(arr[i].begin, PointType.BEGIN));
			beginsAndEnds.add(2 * i + 1, new IntervalPoint<T>(arr[i].end, PointType.END));
		}
		
		Collections.sort(beginsAndEnds, new Comparator<IntervalPoint<T>>() {
			@Override
			public int compare(IntervalPoint<T> o1, IntervalPoint<T> o2) {
				if (o1 == o2)	return 0;
				if (o1 == null)	return -1;
				if (o2 == null) return 1;
				
				int result = o1.value.compareTo(o2.value);
				if (result != 0) {
					return result;
				}

				if (o1.type == o2.type) {
					return 0;
				}
				else if (o1.type == PointType.BEGIN){
					return 1;
				}
				else {
					return -1;
				}
			}
		});
		
		int count = 0;
		int max = 0;
		int index = 0;
		
		for (int i = 0; i < beginsAndEnds.size(); ++i) {
			if (beginsAndEnds.get(i).type == PointType.BEGIN) {
				++count;
				if (count > max) {
					max = count;
					index = i;
				}
				
			}
			else if (beginsAndEnds.get(i).type == PointType.END) {
				--count;
			} 
		}
		
		return new Interval<T>(beginsAndEnds.get(index).value, beginsAndEnds.get(index+1).value);
	}
	
	// Only for integer
	public static Interval<Integer> findMostOverLappedIntervalInt(Interval<Integer>[] arr) {
		assert (arr != null && arr.length > 0);
		
		Map<Integer, Integer> beginnings = new HashMap<Integer, Integer>();
		Map<Integer, Integer> endings = new HashMap<Integer, Integer>();

		int[] beginsAndEnds = new int[arr.length * 2];
		
		for (int i = 0; i < arr.length; ++i) {
			beginsAndEnds[2 * i] = arr[i].begin;
			beginsAndEnds[2 * i + 1] = arr[i].end;
			if (beginnings.containsKey(arr[i].begin)) {
				beginnings.put(arr[i].begin, beginnings.get(arr[i].begin) + 1);
			}
			else {
				beginnings.put(arr[i].begin, 1);
			}
			
			if (endings.containsKey(arr[i].end)) {
				endings.put(arr[i].end, endings.get(arr[i].end) + 1);
			}
			else {
				endings.put(arr[i].end, 1);
			}
		}
		
		Arrays.sort(beginsAndEnds);
		
		int count = 0;
		int max = 0;
		int index = 0;
		
		for (int i = 0; i < beginsAndEnds.length; ++i) {
			if (beginnings.containsKey(beginsAndEnds[i])) {
				++count;
				int n = beginnings.get(beginsAndEnds);
				if (n == 1) {
					beginnings.remove(beginsAndEnds[i]);
				}
				else {
					beginnings.put(beginsAndEnds[i], n - 1);
				}
			}
			else if (endings.containsKey(beginsAndEnds[i])) {
				--count;
				int n = endings.get(beginsAndEnds[i]);
				if (n == 1) {
					endings.remove(beginsAndEnds[i]);
				}
				else {
					endings.put(beginsAndEnds[i], n - 1);
				}
			}
			
			if (count > max) {
				max = count;
				index = i;
			}
		}
		
		return new Interval<Integer>(beginsAndEnds[index], beginsAndEnds[index + 1]);
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		//Interval<Double>[] intervals = CreateUtils.randNonNegIntIntervals(8, 50);
//		PrintUtils.printArray(intervals);
//		System.out.println(findMostOverLappedInterval(intervals));
		
		@SuppressWarnings("unchecked")
		Interval<Double>[] intervals = new Interval[5];
		intervals[0] = new Interval<Double>(8.0, 10.0);
		intervals[1] = new Interval<Double>(7.0, 8.0);
		intervals[2] = new Interval<Double>(3.0, 16.0);
		intervals[3] = new Interval<Double>(2.0, 4.0);
		intervals[4] = new Interval<Double>(1.0, 5.0);		
		PrintUtils.printArray(intervals);
		Interval<Double> result = findMostOverLappedInterval(intervals);
		
		System.out.printf("[%f, %f]", result.begin, result.end);

	}


}
